#include <iostream>
#include <algorithm>
#include <list>
#include <forward_list>
#include <numeric>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
int binarySearch(vector<int> &arr, int target)
{
    int left = 0;
    int right = arr.size() - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (left + right) >> 1;
        if (arr[mid] > target)
        {
            right = mid - 1;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
Node *reverseForwardList(Node *head)
{
#if 0   /*指针写法*/
    if (head == nullptr)
        return nullptr;
    Node *pre = nullptr;
    Node *cur = head;
    while (cur != nullptr)
    {
        Node *temp = cur;
        cur = cur->next;
        temp->next = pre;
        pre = temp;
    }
    return pre;
#elif 1 /*递归写法*/
    /*检查空or递归到链表的尾部*/
    if (head == nullptr || head->next == nullptr)
        return head;

    Node *tail = reverseForwardList(head->next);

    head->next->next = head;
    head->next = nullptr;
    return tail;
#endif
}
void print(int num)
{
    cout << num << " ";
}
class Func
{
private:
public:
    void operator()(int num)
    {
        cout << num << " ";
    }
};

int main()
{
    /*非变动算法*/
    vector<int> arr = {1, 2, 3, 4, 3};
#if 0   /*lambda表达式*/
    
    for_each(arr.begin(), arr.end(),
             [](int num)
             {
                 cout << num << "\t";
             });
#elif 0 /*函数指针*/

    for_each(arr.begin(), arr.end(), print);
#elif 0 /*仿函数*/

    Func f;
    for_each(arr.begin(), arr.end(), f);
    cout << endl;
#elif 0 /*count()计算个数*/
    int res = count(arr.begin(), arr.end(), 3);
    cout << res << endl;
#elif 0 /*count_if()*/
    int res = count_if(arr.begin(), arr.end(),
                       [](int num) -> bool
                       { return num >= 3; });
    cout << res << endl;
#elif 0 /*max_element&&min_element*/
    int res = *max_element(arr.begin(), arr.end());
    cout << res << endl;
    res = *min_element(arr.begin(), arr.end());
    cout << res << endl;
#elif 0 /*find:找到区间的符合条件的第一个元素*/
    // cout << distance(arr.begin(), find(arr.begin(), arr.end(), 3));
    cout << *find(arr.begin(), arr.end(), 1);
    cout << endl;
#elif 0 /*find_if:找到符合条件的第一个元素*/
    cout << *find_if(arr.begin(), arr.end(), [](int num)
                     { return num > 3 && num % 2 == 1; });

    cout << endl;
#elif 0 /*search_n:在这个区间找到连续的2个3*/
    cout << *search_n(arr.begin(), arr.end(), 2, 3); /*在这个区间找到连续的2个3*/
    cout << endl;
#elif 0 /*search:查找子集*/
    // vector<int> arr2 = {2, 3};
    string s1 = "helloworld";
    string s2 = "world";
    cout << *search(s1.begin(), s1.end(), s2.begin(), s2.end()); /*在这个区间找到连续的2个3*/
    cout << endl;
#elif 0 /*find_end,找到子区间出现的最后一次位置*/
    string s1 = "helloworld";
    string s2 = "rld";
    auto it = find_end(s1.begin(), s1.end(), s2.begin(), s2.end());
    cout << distance(s1.begin(), it);
    cout << endl;
#elif 0 /*find_first_of:找到子区间中在父区间出现的第一个元素*/
    vector<int> array1 = {33, 2, 45, 78, 26};
    vector<int> array2 = {6, 45, 5};
    cout << *find_first_of(array1.begin(), array1.end(), array2.begin(), array2.end());
    cout << endl;
#elif 0 /*adjacent_find:查找两个相邻相同元素的的第一个迭代器*/
    vector<int> array1 = {33, 2, 45, 45, 26};
    vector<int> array2 = {6, 45, 5};
    cout << *adjacent_find(array1.begin(), array1.end());
    cout << endl;
#elif 0 /*判断两个区间是否相等*/
    vector<int> array1 = {33, 2, 45, 45, 26};
    vector<int> array2 = {6, 45, 5};
    cout << equal(array1.begin(), array1.end(), array2.begin(), array2.end());
    cout << endl;
#elif 0 /*mismatch:找到两个区间第一个不相等的地方，返回值是pair*/
    string s1 = "hello";
    string s2 = "helwl";

    auto it = mismatch(s1.begin(), s1.end(), s2.begin(), s2.end());
    cout << *it.first << endl;
    cout << *it.second << endl;

#elif 0 /*变动性算法*/ /*for_each*/
    vector<int> arr1 = {1, 2, 3};
    for_each(arr1.begin(), arr1.end(), [](int &num)
             {
        num++;
        cout<<num<<" "; });
    cout << endl;
#elif 0                /*copy*/
    vector<int> arr1 = {1, 2, 3};
    list<int> l;
    l.resize(3);
    copy(arr1.begin(), arr1.end(), l.begin());
    for_each(l.begin(), l.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*copy_backward:从尾部开始拷贝*/
    vector<int> arr1 = {1, 2, 3};
    list<int> l;
    l.resize(2);
    copy_backward(arr1.begin(), arr1.end(), l.end()); // 第三个参数是待copy的end
    for_each(l.begin(), l.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*transform:拷贝数据并做出处理*/
    vector<int> arr1 = {1, 2, 3};
    list<int> l;
    l.resize(4);
    transform(arr1.begin(), arr1.end(), l.begin(), [](int num)
              { return num * 2; }); // 第三个参数是待copy的end
    for_each(l.begin(), l.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*merge:合并两个区间并排序*/
    vector<int> arr1 = {1, 2, 3};
    list<int> l;
    l.resize(3);
    transform(arr1.begin(), arr1.end(), l.begin(), [](int num)
              { return num * 2; }); // 第三个参数是待copy的end
    vector<int> arr2(6);
    /*自动排序*/
    merge(arr1.begin(), arr1.end(), l.begin(), l.end(), arr2.begin()); // 第三个参数是待copy的end
    for_each(arr2.begin(), arr2.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*swap_ranges:交换两个区间的值*/
    vector<int> arr1 = {1, 2, 3};
    list<int> l;
    l.resize(3);
    transform(arr1.begin(), arr1.end(), l.begin(), [](int num)
              { return num * 2; }); // 第三个参数是待copy的end

    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    for_each(l.begin(), l.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
    swap_ranges(arr1.begin(), arr1.end(), l.begin()); // 第三个参数是待copy的end
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    for_each(l.begin(), l.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*fill:将整个区间的值都设置成指定值*/
    vector<int> arr1 = {1, 2, 3};
    fill(arr1.begin(), arr1.end(), 0);
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0                /*fill_n:从指定位置开始的第n值都为指定值*/
    vector<int> arr1 = {1, 2, 3};
    fill_n(arr1.begin(), 3, 99);
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;

#elif 0 /*generate:改变区间的值*/
    vector<int> arr1 = {1, 2, 3};
    generate(arr1.begin(), arr1.end(), []()
             { return 99; });
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*generate_n:改变从指定位置开始的n个值*/
    vector<int> arr1 = {1, 2, 3};
    generate_n(arr1.begin(), 3, []()
               { return 99; });
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*replace:修改指定位置的值*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    replace(arr1.begin(), arr1.end(), 3, 100); // 将第3个位置的值修改为100
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*replace_if:修改指定位置的值*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    replace_if(
        arr1.begin(), arr1.end(),
        [](int num)
        {
            return num % 2 == 0;
        },
        100); // 将偶数值修改为100
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*移除性算法:remove*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7, 8};
    // arr1.erase(arr1.end()-1);
    remove(arr1.begin(), arr1.end(), 3);
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*移除性算法:remove_if*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7, 8};
    // arr1.erase(arr1.end()-1);
    remove_if(arr1.begin(), arr1.end(), [](int num)
              { return num % 2 == 0; });
    for_each(arr1.begin(), arr1.end(), [](int &num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*移除性算法:unique*/
    vector<int> arr1 = {1, 2, 3, 7, 7};
    vector<int> arr2(5);
    unique_copy(arr1.begin(), arr1.end(), arr2.begin());
    for_each(arr2.begin(), arr2.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*变序型算法:reverse,反转容器*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    reverse(arr1.begin(), arr1.end()); /*容器必须支持逆序迭代器*/
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*变序型算法:rotate,旋转容器*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};              /*左旋*/
    rotate(arr1.begin(), arr1.begin() + 2, arr1.end()); /*容器必须支持逆序迭代器*/
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*变序型算法:next_permutation,求下一个排列*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    next_permutation(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    next_permutation(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    next_permutation(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0
    srand(time(nullptr));
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    random_shuffle(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;

#elif 0 /*partition：分组函数,将符合要求的数据放到前面*/
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    //  partition(arr1.begin(), arr1.end(), [](int num)
    // { return num % 2 == 0; });
    /*借用了额外空间*/
    stable_partition(arr1.begin(), arr1.end(), [](int num)
                     { return num % 2 == 0; });
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*sort：排序*/
    /*数量不超过16：插入排序， \
     *超过16：                         \
     *递归深度没到0：快速排序  \
     * 递归深度到0：堆排序       \
     */

    srand(time(nullptr));
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    random_shuffle(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    // sort(arr1.begin(), arr1.end(), greater<int>());
    // stable_sort(arr1.begin(), arr1.end(), [](int a, int b)
    //             { return a > b; });
    /*
     *stable_sort()
     *长度<15插排
     *else
     * 插排和归并
     */
    stable_sort(arr1.begin(), arr1.end(), greater<int>());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*partial_sort:部分排序，前n个数排序,底层：堆排序*/
    srand(time(nullptr));
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    random_shuffle(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    partial_sort(arr1.begin(), arr1.begin() + 3, arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*nth_element:只排第n个数，底层:堆排序*/
    srand(time(nullptr));
    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    random_shuffle(arr1.begin(), arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    nth_element(arr1.begin(), arr1.begin() + 3, arr1.end());
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*已序区间算法:binarySearch*/

    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    // if (binary_search(arr1.begin(), arr1.end(), 3))
    // {
    //     cout << "存在\n";
    // }
    // else
    // {
    //     cout << "不存在\n";
    // }
    int res = binarySearch(arr1, 3);
    cout << "res = " << res << endl;
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*已序区间算法:includes*/

    vector<int> arr1 = {1, 2, 3, 4, 5, 6};
    vector<int> arr2 = {1, 2};

    cout << includes(arr1.begin(), arr1.end(), arr2.begin(), arr2.end()) << endl;
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*已序区间算法:lower_bound,>=给出的数*/
    /*已序区间算法:upper_bound,>给出的数*/

    vector<int> arr1 = {1, 2, 3, 4, 5, 6};

    cout << *lower_bound(arr1.begin(), arr1.end(), 3) << endl;
    cout << *upper_bound(arr1.begin(), arr1.end(), 3) << endl;
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*已序区间算法:equal_range*/

    vector<int> arr1 = {1, 2, 2, 3, 4, 5, 6};
    vector<int> arr2 = {1, 2};
    auto pair = equal_range(arr1.begin(), arr1.end(), 2);
    cout << distance(arr1.begin(), pair.first) << " " << distance(arr1.begin(), pair.second) << endl;
    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*已序区间算法:       \
        set_union求并集 \        \
        set_intersection求交集 \ \
        set_difference求补集     \
         */

    vector<int> arr1 = {1, 2, 2, 3, 4, 5, 6};
    vector<int> arr2 = {1, 2};
    vector<int> arr3(10);
    set_union(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    for_each(arr3.begin(), arr3.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    arr3.clear();
    arr3.resize(10, 0);
    set_intersection(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    for_each(arr3.begin(), arr3.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    arr3.clear();
    arr3.resize(10, 0);
    set_difference(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    for_each(arr3.begin(), arr3.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
    arr3.clear();
    arr3.resize(10, 0);
    set_symmetric_difference(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
    for_each(arr3.begin(), arr3.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*todo...*/
    vector<int> arr1 = {1, 2, 3, 2, 4, 5, 6};

    for_each(arr1.begin(), arr1.end(), [](int num)
             { cout << num << " "; });
    cout << endl;
#elif 0 /*accumulate:做加法*/
    vector<int> arr1 = {1, 2, 3};
    // string s1 = "hello";
    // string s2 = "wrold";
    int sum = 0;
    cout << accumulate(arr1.begin(), arr1.end(), 0) << endl;
    // cout << accumulate(s1.begin(), s1.end(), s2) << endl;
#elif 1 /*inner_product:a1a2+b1b2,向量乘法*/
    vector<int> arr1 = {1, 2};
    vector<int> arr2 = {3, 4};
    int sum = 0;
    cout << inner_product(arr1.begin(), arr1.end(), arr2.begin(), 0) << endl;

#endif
    return 0;
}